<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>最小生成树练习-Prim算法</title>
    <h1>最小生成树练习-Prim算法</h1>
    <script src="https://d3js.org/d3.v7.min.js"></script>
    <style>
        body {
            font-family: 'Arial', sans-serif;
            background-color: #f7f7f7;
            padding: 20px;
        }

        #status {
            font-size: 20px;
            font-weight: bold;
            margin-top: 10px;
            color: green;
        }

        #clickedEdges {
            margin-top: 20px;
            padding: 10px;
            background-color: #fff;
            border-radius: 8px;
            box-shadow: 0 2px 5px rgba(0, 0, 0, 0.1);
        }

        #correctPaths {
            margin-top: 20px;
            padding: 10px;
            background-color: #fff;
            border-radius: 8px;
            box-shadow: 0 2px 5px rgba(0, 0, 0, 0.1);
        }

        .edge {
            cursor: pointer;
            transition: stroke 0.3s ease, stroke-width 0.3s ease;
        }

        .node {
            cursor: pointer;
            fill: #3498db; /* 蓝色 */
            stroke: #333;
            stroke-width: 2px;
        }

        .edgeLabel {
            font-size: 12px;
            fill: #333;
            font-weight: bold;
            text-anchor: middle;
            pointer-events: none;
        }

        .edge.correct {
            stroke: #2ecc71; /* 绿色 */
        }

        .edge.wrong {
            stroke: #e74c3c; /* 红色 */
        }

        .node:hover {
            fill: #2980b9;
        }

        .edge:hover {
            stroke: #3498db;
        }
    </style>
</head>
<body>

<div id="status">点击边开始练习。</div>
<svg width="800" height="600"></svg>

<div id="clickedEdges">
    <a>点击的边：</a>
</div>
<div id="correctPaths"></div>
<div id="mstEdges"></div>

<script>
// 随机生成图的节点和边
function generateRandomGraph(numNodes, maxEdgeWeight) {
    const nodes = [];
    const edges = [];
    
    // 随机生成节点
    for (let i = 0; i < numNodes; i++) {
        nodes.push({
            id: String.fromCharCode(65 + i), // 使用字母A, B, C...作为节点标识
            x: Math.random() * 600 + 100, // 随机x坐标，确保不会超出svg边界
            y: Math.random() * 400 + 100, // 随机y坐标
        });
    }

    // 随机生成边
    for (let i = 0; i < numNodes; i++) {
        for (let j = i + 1; j < numNodes; j++) {
            const weight = Math.floor(Math.random() * maxEdgeWeight) + 1; // 随机生成边的权重
            edges.push({
                source: nodes[i].id,
                target: nodes[j].id,
                weight: weight,
            });
        }
    }

    return { nodes, edges };
}

// 计算最小生成树的边集合，使用 Kruskal 算法
function getMSTEdges(graph) {
    const edges = graph.edges.sort((a, b) => a.weight - b.weight); // 按权重升序排序
    const parent = {};
    const rank = {};

    // 初始化并查集
    function find(node) {
        if (parent[node] === undefined) {
            parent[node] = node;
            rank[node] = 0;
        }
        if (parent[node] !== node) {
            parent[node] = find(parent[node]);
        }
        return parent[node];
    }

    function union(node1, node2) {
        const root1 = find(node1);
        const root2 = find(node2);

        if (root1 !== root2) {
            if (rank[root1] > rank[root2]) {
                parent[root2] = root1;
            } else if (rank[root1] < rank[root2]) {
                parent[root1] = root2;
            } else {
                parent[root2] = root1;
                rank[root1]++;
            }
            return true;
        }
        return false;
    }

    const mstEdges = [];
    for (const edge of edges) {
        if (union(edge.source, edge.target)) {
            mstEdges.push(edge);
        }
    }
    return mstEdges; // 返回最小生成树的边集合
}

// 使用随机生成的图
const graph = generateRandomGraph(5, 10); // 生成一个5个节点的图，边的权重最大为10

// 获取最小生成树的边
const mstEdges = getMSTEdges(graph);

// 全局变量，记录用户点击的边
let userClickedEdges = [];

// 画图
const svg = d3.select('svg');



// 创建节点
const nodeElements = svg.selectAll('.node')
    .data(graph.nodes)
    .enter().append('circle')
    .attr('class', 'node')
    .attr('r', 20)
    .attr('cx', d => d.x)
    .attr('cy', d => d.y)
    .attr('fill', '#3498db')  // 设置为蓝色
    .attr('stroke', '#333')
    .attr('stroke-width', 2);

// 在节点上添加字母标识
svg.selectAll('.nodeLabel')
    .data(graph.nodes)
    .enter().append('text')
    .attr('class', 'nodeLabel')
    .attr('x', d => d.x)
    .attr('y', d => d.y)
    .attr('dy', -25)  // 小幅上移，以避免重叠
    .attr('text-anchor', 'middle')
    .attr('font-size', 16)
    .attr('fill', '#333')
    .text(d => d.id);

// 创建边
const edgeLines = svg.selectAll('.edge')
    .data(graph.edges)
    .enter().append('line')
    .attr('class', 'edge')
    .attr('x1', d => graph.nodes.find(node => node.id === d.source).x)
    .attr('y1', d => graph.nodes.find(node => node.id === d.source).y)
    .attr('x2', d => graph.nodes.find(node => node.id === d.target).x)
    .attr('y2', d => graph.nodes.find(node => node.id === d.target).y)
    .attr('stroke-width', 2)
    .attr('stroke', '#7f8c8d')
    .on('click', function(event, d) {
        const status = document.getElementById('status');
        const clickedEdgeLabel = `${d.source}-${d.target}`;

        // 记录点击的边
        const clickedEdgeText = document.createElement("a");
        clickedEdgeText.innerText = `${clickedEdgeLabel}->`;
        document.getElementById("clickedEdges").appendChild(clickedEdgeText);

        // 更新边的颜色
        d3.select(this).style("stroke", "gray").style("stroke-width", 4).transition()
            .duration(500) // 动画效果
            .ease(d3.easeElasticOut)
            .attr('stroke-width', 3)
            .style('stroke', 'gray');

        // 判断当前点击的边是否是最小生成树的下一个边
        const clickedEdge = { source: d.source, target: d.target };
        
        // 在mstEdges中找到当前用户应该点击的边
        const expectedEdge = mstEdges[userClickedEdges.length]; // 期待的边
        const isCorrectEdge = (clickedEdge.source === expectedEdge.source && clickedEdge.target === expectedEdge.target) ||
                              (clickedEdge.source === expectedEdge.target && clickedEdge.target === expectedEdge.source);

        if (isCorrectEdge) {
            // 如果点击的边符合顺序，记录点击的边
            userClickedEdges.push(clickedEdgeLabel);

            // 打印当前用户点击的所有边
            console.log(userClickedEdges);

            // 显示当前正确的路径
            const correctPathsText = document.createElement("a");
            correctPathsText.innerText = `正确的路径: ${userClickedEdges.join(' -> ')}`;
            document.getElementById("correctPaths").innerHTML = '';  // 清空之前的路径
            document.getElementById("correctPaths").appendChild(correctPathsText);

            // 检查点击的边数是否等于MST的边数
            if (userClickedEdges.length === mstEdges.length) {
                status.innerText = '操作正确！';
            } else {
                status.innerText = '继续点击边，直到完成最小生成树。';
            }
        } else {
            status.innerText = '错误。';  // 如果顺序错误，提示错误
        }
    });

// 在边上添加权重标签
svg.selectAll('.edgeLabel')
    .data(graph.edges)
    .enter().append('text')
    .attr('class', 'edgeLabel')
    .attr('x', d => (graph.nodes.find(node => node.id === d.source).x + graph.nodes.find(node => node.id === d.target).x) / 2)
    .attr('y', d => (graph.nodes.find(node => node.id === d.source).y + graph.nodes.find(node => node.id === d.target).y) / 2)
    .text(d => d.weight)
    .attr('fill', '#333')
    .attr('font-size', '14px')
    .attr('font-weight', 'bold')
    .attr('text-anchor', 'middle');

    // 显示 mstEdges 在页面下方
function updateMSTEdgesDisplay() {
    const mstEdgesContainer = document.getElementById("mstEdges");

    // 清空当前内容
    mstEdgesContainer.innerHTML = '';

    // 创建一个无序列表展示 MST 边
    const list = document.createElement("ul");

    mstEdges.forEach(edge => {
        const listItem = document.createElement("li");
        listItem.innerText = `${edge.source} - ${edge.target} (Weight: ${edge.weight})`;
        list.appendChild(listItem);
    });

    // 将列表添加到 mstEdges 容器
    mstEdgesContainer.appendChild(list);
}

// 在初始化时更新 mstEdges 显示
updateMSTEdgesDisplay();

</script>

</body>
</html>
